Queues are widely used for buffering or storing data. Examples of the data can include, but are not limited to, program instructions that require execution, web queries, and computer applications. A queue can be accessed by multiple processes. The processes can also be referred to as threads. One such example of the queue is a first in, first out (FIFO) queue where a writer thread inserts the data into the FIFO queue. A reader thread subsequently retrieves the data from the FIFO queue. The data is inserted at a tail end of the FIFO queue and the data is retrieved from a head end of the FIFO queue. Further, process of inserting data into the FIFO queue is referred to as enqueuing and the process of retrieving data from the FIFO queue is referred to as dequeuing. The data retrieved by the reader thread is transmitted for further processing.
Multiple writer threads try to insert multiple data into the FIFO queue simultaneously. In such a case, the multiple data is overwritten in the FIFO queue resulting in loss of the data prior to processing. One method to overcome the above limitation is to employ a hard lock to the FIFO queue. The hard lock ensures merely one writer thread or one reader thread for enqueuing or dequeuing respectively at one time instant. In one example, a first writer thread can obtain the hard lock and insert the data into the FIFO queue. While the first writer thread, possesses the hard lock, other writer threads or the reader thread are unable to access the FIFO queue at that time instant. Further, the writer threads except the first writer thread possessing the hard lock are put to sleep mode. Upon inserting the data into the FIFO queue, the first writer thread releases the hard lock. The hard lock thus released is then possessed by one of the other writer threads or the reader thread to enter data into the FIFO queue or to retrieve the data from the FIFO queue respectively. Further, the writer threads and the reader thread are forced to wait until acquiring the hard lock to enqueue the data and to dequeue the data respectively. Furthermore, using the hard locks for implementing the FIFO queue requires a call to a kernel of an operating system (OS) which is expensive in terms of central processing unit (CPU) cycle usage.
In another queue implementation a soft lock is used while inserting the data into the FIFO queue. The soft lock can be implemented using software objects or software functions. One or more writer threads can attempt to enqueue the data simultaneously. Further, one or more reader threads can also attempt to dequeue the data simultaneously. In such cases, the writer threads and reader threads may attempt to access the priority queue simultaneously. In soft locks, an atomic operation is implemented to ensure that a single writer thread or a reader thread is capable of accessing the priority queue at one time instant. In one example, a current writer thread wishes to modify the FIFO queue by inserting a data into the FIFO queue. Prior to modifying, the current writer thread stores a current state entry value of the FIFO queue and further the current writer thread performs necessary processing of the data. The current writer thread upon processing, checks the current state entry value of the FIFO queue over again. A compare and swap operation (CAS) is performed to check the current state entry value of the FIFO queue. If the current state entry value is not modified then the current writer thread can insert the data into the FIFO queue. Further, if the current state entry value has been modified then CAS would fail and hence the current writer thread cannot modify the FIFO queue. Thus, the current writer thread is required to repeat the processing of the data and further perform the CAS to determine if the current state entry value has been modified. When there is a contention between multiple writer threads to insert the data into the FIFO queue, while one writer thread succeeds and is under the process of inserting the data into the FIFO queue, the other writer threads would be continuously looping using an atomic operation primitive, to detect that the FIFO queue is not under modification and hence can gain access to the FIFO queue for inserting the data. Further, the reader thread can also dequeue the data from the priority queue, however it is not contention free. Although use of the soft lock provides a lock free implementation, valuable CPU cycles are used unnecessarily for merely re-performing the operations mentioned above. Further, one of the writer threads could get starved and the writer thread that gets starved might end up executing the atomic operation primitive indefinitely.
In the light of the foregoing discussion there is a need for a method and a system for implementing the FIFO queue in a lock free and contention free manner.